Count Ways to Score in a Game

Statement#

Suppose there is a game where a player can score either $1$, $2$, or $4$ points in each turn. Given a total score, $n$, find all the possible ways in which you can score these $n$ points.

Note: You may assume that you can use a specific score as many times as you want. Additionally, the order in which we select scores from the list is significant.

Let's say the total points to be earned are $3$. A player can score this total in the following three ways:

• $1, 1$and $1$, in three turns: $1+1+1 = 3$.

• $1$ and then a $2$, in two turns: $1 + 2 = 3$.

• $2$ and then a $1$, in two turns: $2 + 1 = 3$.

Constraints:

• $0$ <= $n$ <= $900$

Examples#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Recursive Numbers dynamic programming pattern.

Naive approach#

A naive approach to solving this problem would be to make all the possible permutations of available points to reach the target score, so let's first figure out the recurrence relation for this problem.

As we can only score $1$, $2$, or $4$ in each turn, to reach a score of $n$, we can only use increments of $1$, $2$, or $4$ in each turn. To reach a total score of $n$, we have the following three possibilities:

• Number of ways to reach $n - 1$, as we can then add $1$ to reach $n$

• Number of ways to reach $n-2$, as we can then add $2$ to reach $n$

• Number of ways to reach $n-4$, as we can then add $4$ to reach $n$

These all are valid ways to reach a score of $n$. We can now sum them up to get all the possible ways to reach a total score of $n$.

As per the above points, we can derive the following recurrence relation for this problem:

           $S(n)=S(n-1)+S(n-2)+S(n-4)$

Here, $S(n)$ is the number of ways of reaching a total score of $n$.

Now, let's look at the code in the code widget below for the solution we just discussed.

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of this solution is $O(2^n)$.

Space complexity#

The space complexity of this solution is $O(n)$ because each recursive call consumes memory on the stack, and the longest call stack corresponds to the calls starting from $n$, through $n-1$, $n-2$, down to $3$, $2$ and $1$.

Optimized solution using dynamic programming#

As the recursive solution to this problem is very costly, let's see if we can reduce this cost in any way. Dynamic programming helps us to avoid recomputing the same subproblems. Let's analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.

• Optimal substructure: If we wanted to find the solution to the problem of counting a total score, $n$, given $p$ different points, and we knew the answer to the $p$ subproblems formed by subtracting each of the $p$ points from the total score S, we could simply sum up the answer to these subproblems, and that would give us the answer to our original problem. Therefore, this problem obeys the optimal substructure property.

• Overlapping subproblems: The algorithm solves the same subproblems again and again, so it does have the second property of dynamic programming as well.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating solutions to subproblems over and over again by storing the subproblem solutions, and reusing the stored solutions when the same subproblem is encountered again. Therefore, the only addition to this algorithm compared to the simple recursive one is the addition of memoization. Specifically, we build the solution top-down and store the found results in a memo array.

The slides below are to help you visualize the process. Here, the green nodes represent recursive calls where stored results are fetched from the memo array:

Now, let's look at the code in the code widget below for the solution we just discussed.

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this solution is $O(n)$.

Space complexity#

The space complexity of this solution is $O(n)$.

Bottom-up solution#

Let’s look at the bottom-up dynamic programming approach to solving this problem. The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here, we iteratively build the solution in a bottom-up direction by storing the results in a fixed-size array.

We first create and initialize the fixed array, dp, that will store our results. Then, we set dp[0] to 1, which is our base case, that is, there is only one way to reach a score of $0$ by not playing any moves.

To calculate the result for any turn, we sum up the number of ways to get a score of $n-1$, $n−2$, and $n-4$. This is similar to our recurrence relation. For example, to find the number of ways to score $5$, we add up dp[5-1], dp[5-2] and dp[5-4]. During the calculations, if at any point, the remaining value needed to reach $n$ becomes negative, we will simply return $0$, as there is no way to reach a negative score.

Let's look at how this technique works for a total score of $5$:

Let's have a look at the code for the bottom-up approach as well.

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this solution is $O(n)$.

Space complexity#

The space complexity of this solution is $O(n)$.